import java.util.Arrays;

public class TestHeap {
    private int[] elem;
    private int usedSize;

    public TestHeap(){
        this.elem = new int[10];
    }


    public void initHeap(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize ++;
        }
    }
    public void createHeap(){
        for (int parent = (usedSize -1 -1)/2; parent >= 0 ; parent--) {
             shiftDown(parent,usedSize);
        }
    }

    private void shiftDown(int parent, int usedSize) {
        int child = 2 * parent + 1;//左孩子下标

        while (child < usedSize) {//保证有左树

            //确保child是孩子节点最大值的下标
            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child++;
            }

            if (elem[parent] < elem[child]) {
                sawp(parent, child);

                //保证换完之后，下面的子树也符合大堆根
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }


    private void sawp( int i, int j) {
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }


   //向大根堆插入一个元素
    public void offer(int val){
        if(usedSize == elem.length){
            this.elem = Arrays.copyOf(elem,2*elem.length );
        }
        this.elem[usedSize] = val;
        shiftUp(usedSize);//向上调整!!!!!!!!!!
        usedSize++;
    }

    private void shiftUp(int child) {
        int parent = (child -1) /2;
        while(child >0) {
            if (elem[parent] < elem[child]) {
                sawp(parent, child);
                child = parent;
                parent = (child -1) /2;
            } else {
                break;
            }
        }
    }

    //删除优先级元素（最大的元素）用向下调整
    public int poll(){
        int tmp = elem[0];
        sawp(0,usedSize-1);//只需要向下调整0这棵树
        usedSize --;
        shiftDown(0,usedSize);
        return tmp;
    }
}
